#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;

int main(int argc, char** argv) {
    int t;
    cin>>t;
    LL K,M;
    while (t--) {
        cin>>K>>M;
        LL res = (K+1) % M;
        LL a=K, b=(K+2), c=(K+1);
        if (a%2==0) a=a/2;
        else if (b%2==0) b=b/2;
        else c=c/2;
        a=a%M; b=b%M; c=c%M;
        res = (res + a*b%M *c%M) % M;
        a=K;
        b=K+1;
        c=2*K+1;
        if (a%2==0) a=a/2;
        else if (b%2==0) b=b/2;
        else c=c/2;
        if (a%3==0) a=a/3;
        else if (b%3==0) b=b/3;
        else c=c/3;
        a=a%M; b=b%M; c=c%M;
        LL tmp = a*b%M*c%M;
        res = (res-tmp)%M;
        res = (res+M)%M;
        cout<<res<<endl;
    }
    return 0;
}
